/*
 *  Heap sort(max binary heap)
 */
package algs4.sort;

public class Heap
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        int n = a.length;
        int m = n - 1;

        for (int i = n / 2; i > 0; i--)
            sink(a, i, m);

        while (m > 1) {
            exch(a, 1, m--);

            sink(a, 1, m);
        }

        int i = 0;
        Comparable v = a[0];

        for (; i < n - 1 && a[i+1].compareTo(v) < 0; i++)
            a[i] = a[i+1];

        a[i] = v;
    }

    // swim and sink version
    public static void sort(Comparable[] a, String ver) {
        int n = a.length;

        for (int i = 2; i < n; i++) {
            int        k = i;
            Comparable v = a[k];
            // swim k
            while (k > 1 && v.compareTo(a[k / 2]) > 0) {
                a[k]  = a[k / 2];
                k    /= 2;
            }

            a[k] = v;
        }

        /* System.out.print("DG: ");
        for (int i = 0; i < a.length; i++) System.out.printf("%2d ", a[i]);
        System.out.println(); */

        for (int i = n - 2; i > 0; i--) {
            // swap first and last elements
            Comparable v = a[i + 1];

            a[i + 1] = a[1];

            // sink 1 to i
            int k = 1;
            int t;
            while ((t = 2 * k) <= i) {
                if (t < i && a[t].compareTo(a[t+1]) < 0) t++;

                if (v.compareTo(a[t]) < 0) {
                    a[k] = a[t];
                    k    = t;
                } else {
                    break;
                }
            }

            a[k] = v;
        }

        // binary insertion sort
        int        lo = 1;
        int        hi = n;
        Comparable v  = a[0];
        while (hi > lo) {
            int mid = (lo + hi) / 2;

            if (v.compareTo(a[mid]) > 0) lo = mid + 1;
            else                         hi = mid;
        }
        for (int i = 1; i < lo; i++) a[i - 1] = a[i];

        a[lo - 1] = v;
    }

    /* Private Static Methods */
    private static void sink(Comparable[] a, int k, int n) {
        int        i;
        Comparable v = a[k];

        while ((i = 2 * k) <= n) {
            if (i < n && a[i].compareTo(a[i+1]) < 0) i++;

            if (a[i].compareTo(v) > 0) {
                a[k] = a[i];
                k    = i;
            } else {
                break;
            }
        }

        a[k] = v;
    }

    private static void exch(Object[] a, int i, int j) {
        Object t = a[i];

        a[i] = a[j];
        a[j] = t;
    }
}
